package sit.engreal.leetcode.problems300;

import org.junit.jupiter.api.Assertions;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * <a href="https://leetcode.cn/problems/implement-stack-using-queues/">225. 用队列实现栈</a>
 */
public class LeetCode225 {
    public static class MyStack {
        Deque<Integer> head = new ArrayDeque<>();
        Deque<Integer> tail = new ArrayDeque<>();

        public MyStack() {

        }

        public void push(int x) {
            if (!tail.isEmpty()) {
                head.addLast(tail.removeFirst());
            }
            tail.addLast(x);
        }

        public int pop() {
            final int top = tail.removeFirst();
            while (!head.isEmpty()) {
                tail.addLast(head.removeFirst());
            }
            if (tail.isEmpty()) {
                return top;
            }
            do {
                final Integer next = tail.removeFirst();
                if (tail.isEmpty()) {
                    tail.addLast(next);
                    return top;
                } else {
                    head.addLast(next);
                }
            } while (true);
        }

        public int top() {
            return tail.getFirst();
        }

        public boolean empty() {
            return tail.isEmpty();
        }
    }

    public static void main(String[] args) {
        {
            final MyStack myStack = new MyStack();
            myStack.push(1);
            myStack.push(2);

            Assertions.assertEquals(2, myStack.top());
            Assertions.assertEquals(2, myStack.pop());
            Assertions.assertFalse(myStack.empty());
        }

        {
            final MyStack myStack = new MyStack();
            myStack.push(1);
            Assertions.assertEquals(1, myStack.pop());
            Assertions.assertTrue(myStack.empty());
        }

    }
}
